import java.util.PriorityQueue;

/*
 * @lc app=leetcode.cn id=2542 lang=java
 *
 * [2542] 最大子序列的分数
 *
 * https://leetcode.cn/problems/maximum-subsequence-score/description/
 *
 * algorithms
 * Medium (46.70%)
 * Likes:    20
 * Dislikes: 0
 * Total Accepted:    1.8K
 * Total Submissions: 3.7K
 * Testcase Example:  '[1,3,3,2]\n[2,1,3,4]\n3'
 *
 * 给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k
 * 的 子序列 对应的下标。
 * 
 * 对于选择的下标 i0 ，i1 ，...， ik - 1 ，你的 分数 定义如下：
 * 
 * 
 * nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。
 * 用公示表示： (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] ,
 * nums2[i1], ... ,nums2[ik - 1]) 。
 * 
 * 
 * 请你返回 最大 可能的分数。
 * 
 * 一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
 * 输出：12
 * 解释：
 * 四个可能的子序列分数为：
 * - 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。
 * - 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。
 * - 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。
 * - 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。
 * 所以最大分数为 12 。
 * 
 * 
 * 示例 2：
 * 
 * 输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
 * 输出：30
 * 解释：
 * 选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * n == nums1.length == nums2.length
 * 1 <= n <= 10^5
 * 0 <= nums1[i], nums2[j] <= 10^5
 * 1 <= k <= n
 * 
 * 
 */

// @lc code=start
class Solution {
    // public long maxScore(int[] nums1, int[] nums2, int k) {
    //     int num1_middle[]=new int[nums1.length-k+1];
    //     int num2_middle[]=new int[nums2.length-k+1];
    //     int middle=0;
    //     for (int i = 0; i < k; i++) {
    //         middle+=nums1[i];
    //     }
    //     num1_middle[0]=middle;
    //     for (int i = 1; i < num2_middle.length; i++) {
    //         middle+=nums1[i+k-1];
    //         middle-=nums1[i-1];
    //         num1_middle[i]=middle;
    //     }
    //     PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((a,b)->a-b);
    //     for (int i = 0; i < k; i++) {
    //         priorityQueue.add(nums2[i]);
    //     }
    //     num2_middle[0]=priorityQueue.peek();
    //     for (int i = 1; i < num2_middle.length; i++) {
    //         priorityQueue.remove(nums2[i-1]);
    //         priorityQueue.add(nums2[i+k-1]);
    //         num2_middle[i]=priorityQueue.peek();
    //     }
    //     int res=Integer.MIN_VALUE;
    //     for (int i = 0; i < num2_middle.length; i++) {
    //         res=Math.max(res, num1_middle[i]*num2_middle[i]);
    //     }
    //     return res;
    // }
    public long maxScore(int[] nums1, int[] nums2, int k) {
        //贪心算法
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((a,b)->(b-a));
        for (int i0 : nums1) {
            priorityQueue.add(i0);
        }
        long res=0;
        for (int i = 0; i < k; i++) {
            res+=priorityQueue.poll();
        }
        priorityQueue=new PriorityQueue<>();
        for (int i0 : nums2) {
            priorityQueue.add(i0);
        }
        for (int i = 0; i < k-1; i++) {
            priorityQueue.poll();
        }
        return priorityQueue.peek()*res;
    }
}
// @lc code=end

